A portion of the disclosure of this patent document contains material that is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent disclosure, as it appears in the Patent and Trademark Office patent files or records, but otherwise reserves all copyright rights whatsoever.
The present invention generally relates to a method for detecting changes to a system state in a domain represented by a rules-based knowledge base.
A knowledge-based system uses knowledge to solve problems. It is capable of distinguishing between knowledge itself and a knowledge interpreter, which is called an Inference Engine.
Knowledge itself can be represented by two distinct sets of information. The first is a set of domain-specific data about the problem and the environment, the confidence measures and the xe2x80x9cdead endsxe2x80x9d in the environment. The second set of information is a set of rules that express the conditions necessary to regulate the individual pieces of data in the first set, wherein the individual pieces of data represent facts about a steady state representation of the domain.
The Inference Engine is responsible for the execution process. The Inference Engine may employ some of the following principles:
Conflict resolution strategy that specifies which rule to fire first. Among commonly used strategies are the last recently used rule strategy or the most recently used rule strategy, etc.
Efficient pattern matching like the Markov Algorithm, that controls the search using a predefined order of rules to fire or the Rete Algorithm that speeds up the Markov Algorithm by looking only for changes in matches rather than for every rule every time.
Execution of the Right-Hand-Side of rules, which facilitates certain kind of prediction of the possible behavior.
Prior art in the area of this invention includes knowledge being represented by a rooted acyclic directed graph, the Rete; where the nodes, with the exception of the root, depict patterns. A pattern is a unique combination of rules that lead up to a node from the root node in the acyclic directed graph. Paths from the root to the nodes, represent the left-hand side of the rules that make up the patterns. Information is stored at each node about the facts satisfied by the patterns of the nodes in the paths from the root up to and including the current node. This information is a relation representing the possible values of the variables occurring in the patterns in the path. Such a form of knowledge representation suffers from the enormous memory requirements for storing successively larger nodes since information stored at each node in the Rete network is the cumulative information stored at all the nodes before it in the path leading up to that node from the root node.
The Rete Algorithm, adopted by most knowledge processing systems, keeps up to date the information associated with the nodes in the graph. When a fact is added or removed from the corking memory, a token representing the fact and operation is entered at the root of the graph and propagated to its leaves, modifying as appropriate, the information associated with the nodes. This requires considerable processor time and memory resources devoted to propagating the change through all the nodes in the network before the rules affected by the change are identified and queued up for firing.
A need was felt to use a model-based approach that would allow the user to define relationships between rules and data. Thus, any update to the entire knowledge base could be made by applying that update to the root objects in the knowledge base and this update would result in all objects related to the root object being updated and so on. It was felt that a model-based approach to representation of domains would make the task of manipulating data and rules very simple.
An object of the present invention is to provide an object-oriented method of mapping alterations in system state objects to knowledge-base objects called rules, both of which are part of an object-oriented model of the domain resident in a persistent repository.
Another object of the present invention is to provide an object oriented method of evaluating only those rules that have been affected by a state change.
Still another object of the present invention is to provide an object oriented method of allowing an AgendaQueue object to retain, for further processing, only those affected rules whose all rule conditions have been satisfied.
These and other objects, features and advantages, which will become apparent as the invention is described in detail below, are provided in a computer system executing a repository program and having a storage means, a method for mapping alterations in system state to rules, both of which are part of an object-oriented model resident in a persistent repository. The method includes storing in the persistent storage means the model comprising a set of rules and a set of facts defining event states, both of which are stored as objects. The set of rules and said set of facts comprise an object-oriented representation of the model. Next, a set of commands representing an extensible inference engine are loaded as mete objects into the persistent storage. The method accepts as inputs events representing alterations in the set of facts. All of the events are retained and the events are mapped to the set of rules for deriving a list of affected rules, which are evaluated to determine if they have been qualified. Only those affected rules determined as qualified are saved for further processing.
Still other objects, features and advantages of the present invention will become readily apparent to those skilled in the art from the following detailed description, wherein is shown and described only the preferred embodiment of the invention, simply by way of illustration of the best mode contemplated of carrying out the invention. As will be realized, the invention is capable of other and different embodiments, and its several details are capable of modifications in various obvious respects, all without departing from the invention. Accordingly, the drawings and description are to be regarded as illustrative in nature, and not as restrictive, and what is intended to be protected by Letters Patent is set forth in the appended claims. The present invention will become apparent when taken in conjunction with the following description and attached drawings, wherein like characters indicate like parts, and which drawings form a part of this application.